package algorithm;

public class T00064 {
    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(new Solution().minPathSum(grid));
    }

    static class Solution {
        private static final int MAX_VAL = 99999;
        public int minPathSum(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
            dp[0][0] = grid[0][0];
            for (int i = 0;i < m;i ++) {
                for (int j = 0;j < n;j ++) {
                    if (i == 0 && j == 0) continue;
                    dp[i][j] = grid[i][j] + Math.min(dist(dp, i - 1, j), dist(dp, i, j - 1));
                }
            }
            return dp[m - 1][n - 1];
        }

        public int dist(int[][] dp, int i, int j) {
            if (i < 0 || j < 0) return MAX_VAL;
            return dp[i][j];
        }
    }
}
